home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / os2 / pccts.zip / HASH.C < prev    next >
C/C++ Source or Header  |  1992-12-08  |  5KB  |  183 lines
  1. /*
  2.  * hash.c
  3.  *
  4.  * Manage hash tables.
  5.  *
  6.  * The following functions are visible:
  7.  *
  8.  *        char    *strdup(char *);        Make space and copy string
  9.  *        Entry     **newHashTable();        Create and return initialized hash table
  10.  *        Entry    *hash_add(Entry **, char *, Entry *)
  11.  *        Entry    *hash_get(Entry **, char *)
  12.  *
  13.  * SOFTWARE RIGHTS
  14.  *
  15.  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
  16.  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
  17.  * company may do whatever they wish with source code distributed with
  18.  * PCCTS or the code generated by PCCTS, including the incorporation of
  19.  * PCCTS, or its output, into commerical software.
  20.  * 
  21.  * We encourage users to develop software with PCCTS.  However, we do ask
  22.  * that credit is given to us for developing PCCTS.  By "credit",
  23.  * we mean that if you incorporate our source code into one of your
  24.  * programs (commercial product, research project, or otherwise) that you
  25.  * acknowledge this fact somewhere in the documentation, research report,
  26.  * etc...  If you like PCCTS and have developed a nice tool with the
  27.  * output, please mention that you developed it using PCCTS.  In
  28.  * addition, we ask that this header remain intact in our source code.
  29.  * As long as these guidelines are kept, we expect to continue enhancing
  30.  * this system and expect to make other tools available as they are
  31.  * completed.
  32.  *
  33.  * ANTLR 1.06
  34.  * Terence Parr
  35.  * Purdue University
  36.  * 1989-1992
  37.  */
  38.  
  39. #include <stdio.h>
  40. #include "hash.h"
  41. #ifdef MEMCHK
  42. #include "trax.h"
  43. #else
  44. #ifdef __STDC__
  45. void *malloc(unsigned int), *calloc(unsigned int, unsigned int);
  46. #else
  47. char *malloc(), *calloc();
  48. #endif
  49. #endif
  50.  
  51. #define StrSame        0
  52. #define fatal(err)                                                            \
  53.             {fprintf(stderr, "%s(%d):", __FILE__, __LINE__);                \
  54.             fprintf(stderr, " %s\n", err); exit(-1);}
  55. #define require(expr, err) {if ( !(expr) ) fatal(err);}
  56.  
  57. static unsigned size = HashTableSize;
  58. static char *strings = NULL;
  59. static char *strp;
  60. static unsigned strsize = StrTableSize;
  61.  
  62. /* create the hash table and string table for terminals (string table only once) */
  63. Entry **
  64. newHashTable()
  65. {
  66.     Entry **table;
  67.     
  68.     table = (Entry **) calloc(size, sizeof(Entry *));
  69.     require( table != NULL, "cannot allocate hash table");
  70.     if ( strings == NULL )
  71.     {
  72.         strings = (char *) calloc(strsize, sizeof(char));
  73.         require( strings != NULL, "cannot allocate string table");
  74.         strp = strings;
  75.     }
  76.     return table;
  77. }
  78.  
  79. /* Given a table, add 'rec' with key 'key' (add to front of list). return ptr to entry */
  80. Entry *
  81. hash_add(table,key,rec)
  82. Entry **table;
  83. char *key;
  84. Entry *rec;
  85. {
  86.     unsigned h=0;
  87.     char *p=key;
  88.     extern Entry *Globals;
  89.     require(table!=NULL && key!=NULL && rec!=NULL, "add: invalid addition");
  90.     
  91.     Hash(p,h,size);
  92.     rec->next = table[h];            /* Add to singly-linked list */
  93.     table[h] = rec;
  94.     return rec;
  95. }
  96.  
  97. /* Return ptr to 1st entry found in table under key (return NULL if none found) */
  98. Entry *
  99. hash_get(table,key)
  100. Entry **table;
  101. char *key;
  102. {
  103.     unsigned h=0;
  104.     char *p=key;
  105.     Entry *q;
  106.     require(table!=NULL && key!=NULL, "get: invalid table and/or key");
  107.     
  108.     Hash(p,h,size);
  109.     for (q = table[h]; q != NULL; q = q->next)
  110.     {
  111.         if ( strcmp(key, q->str) == StrSame ) return( q );
  112.     }
  113.     return( NULL );
  114. }
  115.  
  116. void
  117. hashStat(table)
  118. Entry **table;
  119. {
  120.     static unsigned short count[20];
  121.     int i,n=0,low=0, hi=0;
  122.     Entry **p;
  123.     float avg=0.0;
  124.     
  125.     for (i=0; i<20; i++) count[i] = 0;
  126.     for (p=table; p<&(table[size]); p++)
  127.     {
  128.         Entry *q = *p;
  129.         int len;
  130.         
  131.         if ( q != NULL && low==0 ) low = p-table;
  132.         len = 0;
  133.         if ( q != NULL ) fprintf(stderr, "[%d]", p-table);
  134.         while ( q != NULL )
  135.         {
  136.             len++;
  137.             n++;
  138.             fprintf(stderr, " %s", q->str);
  139.             q = q->next;
  140.             if ( q == NULL ) fprintf(stderr, "\n");
  141.         }
  142.         count[len]++;
  143.         if ( *p != NULL ) hi = p-table;
  144.     }
  145.  
  146.     fprintf(stderr, "Storing %d recs used %d hash positions out of %d\n",
  147.                     n, size-count[0], size);
  148.     fprintf(stderr, "%f %% utilization\n",
  149.                     ((float)(size-count[0]))/((float)size));
  150.     for (i=0; i<20; i++)
  151.     {
  152.         if ( count[i] != 0 )
  153.         {
  154.             avg += (((float)(i*count[i]))/((float)n)) * i;
  155.             fprintf(stderr, "Bucket len %d == %d (%f %% of recs)\n",
  156.                             i, count[i], ((float)(i*count[i]))/((float)n));
  157.         }
  158.     }
  159.     fprintf(stderr, "Avg bucket length %f\n", avg);
  160.     fprintf(stderr, "Range of hash function: %d..%d\n", low, hi);
  161. }
  162.  
  163. /* Add a string to the string table and return a pointer to it.
  164.  * Bump the pointer into the string table to next avail position.
  165.  */
  166. char *
  167. strdup(s)
  168. char *s;
  169. {
  170.     char *start=strp;
  171.     require(s!=NULL, "strdup: NULL string");
  172.  
  173.     while ( *s != '\0' )
  174.     {
  175.         require( strp <= &(strings[strsize-2]),
  176.                  "string table overflow\nIncrease StrTableSize in hash.h and recompile hash.c\n");
  177.         *strp++ = *s++;
  178.     }
  179.     *strp++ = '\0';
  180.  
  181.     return( start );
  182. }
  183.